\documentclass[12pt,a4paper]{article}
% \usepackage[UTF8]{ctex}
% \usepackage{minted}
\usepackage{fontspec}
\usepackage{titletoc}
\usepackage{xeCJK}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{indentfirst} % 中文首段缩进
\usepackage{minted} % 代码块高亮渲染

% \setmainfont[Path=/usr/share/fonts/wenquanyi/wqy-microhei/]{wqy-microhei.ttc}
% \setCJKmainfont[Path=/usr/share/fonts/wenquanyi/wqy-microhei/]{wqy-microhei.ttc}
\setmainfont[Path=/usr/share/fonts/TTF/]{DroidSansFallbackFull.ttf} % DroidSansFallbackFull.ttf Legacy
\setCJKmainfont[Path=/usr/share/fonts/TTF/]{DroidSansFallbackFull.ttf}

\graphicspath{ {img/} }

\usepackage{xcolor}
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    urlcolor=red,
    linktoc=all
}
\definecolor{bg}{rgb}{0.95,0.95,0.95}
\newcommand{\incode}[1]{\mintinline[bgcolor=bg,breaklines]{c}{#1}} % 定义行内代码渲染命令
\newcommand{\codefile}[1]{\inputminted[bgcolor=bg,linenos,tabsize=4,breaklines]{c}{code/#1}} % 定义代码块渲染命令

% \usepackage{tikz} % 作图
% \usetikzlibrary{arrows, positioning, automata}
% \tikzset{ % global config
%     ->, % makes the edges directed
%     >=stealth', % makes the arrow heads bold
%     node distance=3cm, % specifies the minimum distance between two nodes. Change if necessary.
%     every state/.style={thick, fill=gray!10}, % sets the properties for each ’state’ node
%     initial text=$ $, % sets the text that appears on the start arrow
% }

\renewcommand{\baselinestretch}{1.1} % 定义行间距
\parindent 24pt % 重新定义缩进长度
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  lengths
%    下面的命令重定义页面边距，使其符合中文刊物习惯。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\addtolength{\topmargin}{-79pt}
\setlength{\oddsidemargin}{-0.9cm}  % 3.17cm - 1 inch
\setlength{\evensidemargin}{\oddsidemargin}
\setlength{\textwidth}{17.00cm}
\setlength{\textheight}{26.50cm}    % 24.62

\title{PostgreSQL上的Similarity Join实现}
\author{张海斌\thanks{学号 17307130118}}
\begin{document}
\date{2019年6月}

\maketitle

\renewcommand\contentsname{目~录}
\tableofcontents

\section{系统与源码理解}

\incode{src}目录下是PostgreSQL的源代码，其中在\incode{include}目录下，有几个头文件对于本项目有重要的参考意义。首先是\incode{c.h}，这是最基础的一个头文件，其中定义了很多基本的数据类型以及对数据类型进行的宏操作。最初我没有仔细阅读这个文件中的注释，导致项目过程中我很多地方都错误地使用了数据结构，无法得到正确的结果。

在\incode{c.h}中定义了\incode{varlena}结构，还有该结构使用的相关说明注释。变长数据类型都会用到这个结构，而\incode{text}类型是这个结构的别名，所以对\incode{varlena}指针的宏操作都可以用在\incode{text}类型的指针上，有两个关键宏操作分别是\incode{VARDATA_ANY}和\incode{VARSIZE_ANY_EXHDR}，它们分别用来获取\incode{varlena}对象的数据头指针和数据字符串长度大小。我当初没有用这两个宏，然后花费了大量的时间进行 debug。

在\incode{src/include/catelog}目录下，有一个\incode{pg_type.h}头文件，其中定义了各种数据类型的OID数值，相同目录下还有一个\incode{pg_proc.h}头文件。在\incode{src/backend/catelog}目录下的perl脚本文件\incode{genbki.pl}在编译过程中会从\incode{pg_type.h}和\incode{pg_proc.h}等文件中读取数据，并生成\incode{postgres.bki}文件。

\incode{src/backend/utils/fmgrtab.c}文件是由\incode{Gen_fmgrtab.pl}从\incode{pg_proc.h}文件生成的，其中记录了函数管理器的内置函数信息表。表中第一列是函数对应的OID值。我们要添加两个相似性查找函数就需要寻找两个未被占用的OID，作为我们添加的两个函数的OID。当最终编译的时候，能在这个文件中查到我们添加的两个函数就可以说明添加内置函数成功了。

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{pg_proc.h}
	\caption{\incode{pg_proc.h}中\incode{DATA()}中字段控制定义}
	\label{code:pg_proc}
\end{listing}

而内置函数的相关参数都保存在\incode{pg_proc.h}文件中，每一个内置函数都对应一组\incode{DATA()}参数和\incode{DESCR()}描述。我们添加两个函数就要在此添加相应\incode{DATA()}参数和\incode{DESCR()}描述。参数的含义在该文件开头部份给出了定义和注释，见Listing \ref{code:pg_proc}。

最后，要添加的两个内置函数应该放在\incode{src/backend/utils/fmgr/funcapi.c}中。

\section{设计思路与实现方案}

对于Levenshtein Distance的实现，Wikipedia给出的算法是动态规划。对于字符串$a$，$b$（长度分别为$|a|$和$|b|$），只需计算出$(|a|+1)\times(|b|+1)$矩阵$lev$中$lev_{a,b}(|a|,|b|)$的值即为对应的Levenshtein距离。矩阵的状态转移方程如下：
\[
lev_{a,b}(i,j)=\left\{
\begin{array}{lcl}
max(i,j) &  & if min(i,j)=0, \\
min\left\{
	\begin{array}{ll}
	lev_{a,b}(i-1,j)+1 & \\
	lev_{a,b}(i,j-1)+1 & \\
	lev_{a,b}(i-1,j-1)+1_{(a_i\neq b_j)} &
	\end{array}
\right.	& & otherwise.
\end{array}
\right.
\]

\incode{Jaccard Index}是根据相邻两字符组成的bigram，由两字符串的bigram组成的集合的交集和并集元素个数之比定义相似程度。我的实现方法是使用一个以bigram（保存在一个\incode{int}类型的变量中）为排序依据的平衡二叉树来保存每个bigram的相关数据。每个二叉树的节点保存bigram以及一个\incode{char}类型数据\incode{dt}保存它在两个字符串中的出现情况，其初始化的值为0。\incode{char}数据\incode{dt}的第0位和第1位分别表示在字符串a和b中的出现情况。1表示出现，0表示未出现。第一次扫描字符串a，将所有bigram插入到二叉树中，每个节点在初始化后\incode{dt}值为0，将所有不论是否是新插入的节点的\incode{dt}与1取或保存到\incode{dt}中。之后再插入字符串b的所有bigram，对每个bigram对应的节点都将其\incode{dt}与2取或后存放到\incode{dt}中。最后，二叉树中节点个数就是并集元素个数，而所有\incode{dt}值为3的节点的数目就是交集元素个数，由此计算出Jaccard Index。

关于平衡二叉树的选择，我使用了SBT，即Size Balanced Tree。由于SBT中每个节点都会保存对应子树节点个数，所以获取树中节点总数的时间复杂度是$O(1)$。实现的二叉树操作有插入、查找（查找功能没有被使用）以及递归统计\incode{dt}值为\incode{value}的节点个数。

\section{关键代码说明}

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{pg_proc_add.h}
	\caption{\incode{pg_proc.h}中添加的两个新函数的相关信息}
	\label{code:pg_proc_add}
\end{listing}

在\incode{pg_proc.h}文件中，添加了两个相关性计算的函数的相关数据信息（见 Listing \ref{code:pg_proc_add}），\incode{DATA()}中\incode{insert}的OID表示函数对应的OID。插入的数据项由空格分隔，其中第四个数据项在\incode{pg_language.h}中被定义，12表示内置函数，后面的1表示估计执行代价。第一行末尾的i和s分别表示对于给定相同的输入参数，结果不会随行数据的不同或者随不同的扫描而改变，以及可以在后台并行执行多个这个函数。接着的参数2表示函数接收两个参数，后面的0表示带有默认值的参数个数，20表示返回值的数据类型（20对应\incode{INT32}），字符串\incode{"25 25"}表示接收的两个参数的数据类型（25对应\incode{text}），断行第三行第一个参数表示过程源代码的函数名。

对应地，第二个\incode{jaccard_index()}函数除返回值类型是700，表示\incode{float4}外，其它参数基本都相同。

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{levenshtein_distance.c}
	\caption{Levenshtein Distance代码实现}
	\label{code:levenshtein_distance}
\end{listing}

Levenshtein Distance完整代码实现见Listing \ref{code:levenshtein_distance}。其中\incode{str_01}和\incode{txt_02}分别为函数的第一个和第二个参数；\incode{a}和\incode{b}是指向要比较的两个字符串首字符的指针；\incode{m}和\incode{n}分别表示字符串a和b的长度。第9到12行代码为初始化边界条件，第14行到22行根据状态转移方程计算出最终结果\incode{d[m][n]}，最后通过\incode{int32}类型的\incode{result}变量返回函数执行结果。

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{sbtreenode.c}
	\caption{SBT节点定义和基本操作}
	\label{code:SBTreeNode}
\end{listing}

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{free.c}
	\caption{SBT释放节点内存空间}
	\label{code:free}
\end{listing}

Listing \ref{code:SBTreeNode} 列出了SBT节点的完整定义以及初始化一个节点、获取节点对应子树的节点总数、递归统计二叉树中\incode{dt}值等于\incode{value}的节点个数这几个基本功能函数。由于构造树的过程中使用了\incode{malloc()}函数，所以最终需要统一释放SBT分配的内存空间，这部份工作由\incode{freeTree()}函数递归实现，代码见Listing \ref{code:free}。

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{rotate.c}
	\caption{左旋和右旋操作}
	\label{code:rotate}
\end{listing}

Listing \ref{code:rotate} 中展示了和AVL树相同的左旋和右旋操作。

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{maintain.c}
	\caption{维护SBT}
	\label{code:maintain}
\end{listing}

Listing \ref{code:maintain} 中\incode{maintain()}函数是维护SBT，使得对于\incode{*node}节点满足SBT的性质：(1)其左子节点的两个子节点对应的子树节点总数都不超过其右子节点对应子树的节点总数，(2)对称亦然。函数第二个参数表示对SBT的某一性质进行判断，为1表示对性质(2)判断并调整，为0表示对性质(1)判断并调整。具体维护过程就不多赘述了。

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{insert.c}
	\caption{\incode{insert()}函数}
	\label{code:insert}
\end{listing}

Listing \ref{code:insert} 表示插入节点的函数。插入有两种情况，一种是插入的bigram已经在树中了，此时直接返回该节点，其余父节点的\incode{size}不变；另一种是新插入一个节点，此时所有该节点的父节点都要\incode{size}加一。这两种情况通过参数\incode{valid}所指的值进行判断，1为真正插入了一个节点，0为没有插入节点。返回节点指针是方便调用该函数的程序能在后面紧接着对该节点进行修改，如此在\incode{jaccard_index()}函数中无需再使用\incode{search()}函数获取节点指针了。由于\incode{search()}函数没有被调用过，所以我也不贴出代码了（与普通二叉树的查找完去相同）。

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\codefile{jaccard_index.c}
	\caption{\incode{jaccard_index()}函数}
	\label{code:jaccard_index}
\end{listing}

最后就是最重要的\incode{jaccard_index()}函数了（见Listing \ref{code:jaccard_index}）。整体思路与实现方案一致，不过由于在比较的字符串前后要加上\incode{$}符号进行比较，代码相对有些繁复的地方。第10行到第22行是插入第一个字符串的bigram集合，每次插入之后将返回的节点的\incode{dt}值与1取或并写回\incode{dt}；第24行到35行对第二个字符串的bigram集合进行插入，同样也是将节点的\incode{dt}值与2取或并写回\incode{dt}。最后就是计算两个bigram集合交集和并集的元素个数：并集就是SBT中节点个数，直接通过\incode{getSize()}函数即可获得；交集是SBT中节点\incode{dt}值为3的节点的个数，通过调用\incode{getValueCount()}函数获得。最后将交集元素个数与并集元素个数相除得到Jaccard Index并返回。

\section{实验与结果}

\begin{listing}[h]
	\definecolor{bg}{rgb}{0.95,0.95,0.95}
	\inputminted[bgcolor=bg,linenos,tabsize=4,breaklines]{bash}{code/startdb.sh}
	\caption{数据库初始化及启动、执行SQL脚本}
	\label{code:startdb}
\end{listing}

在PostgreSQL数据库安装的目录下，通过Listing \ref{code:startdb}中的命令进行编译、安装等准备工作。

连接上数据库后，使用\incode{\timing}命令开启语句执行时间记录。

测试查询语言：

\begin{minted}[bgcolor=bg,linenos,breaklines]{sql}
select count(*) from restaurantaddress ra, addressphone ap where levenshtein_distance(ra.address, ap.address) < 4;
\end{minted}

\begin{itemize}
	\item 运行时间：37172.944 ms
	\item 正确结果：2592
	\item 实际结果：2582
\end{itemize}

\begin{minted}[bgcolor=bg,linenos,breaklines]{sql}
select count(*) from restaurantphone rp, addressphone ap where jaccard_index(rp.phone, ap.phone) > 0.6;
\end{minted}

\begin{itemize}
	\item 运行时间：21870.710 ms
	\item 正确结果：1653
	\item 实际结果：1653
\end{itemize}

另外执行的四条SQL语句：
\begin{minted}[bgcolor=bg,linenos,breaklines]{sql}
select count(*) from restaurantphone rp, addressphone ap where levenshtein_distance(rp.phone, ap.phone) < 4;
select count(*) from restaurantaddress ra, restaurantphone rp where levenshtein_distance(ra.name, rp.name) < 3;
select count(*) from restaurantaddress ra, restaurantphone rp where jaccard_index(ra.name, rp.name) > 0.65;
select count(*) from restaurantaddress ra, addressphone ap where jaccard_index(ra.address, ap.address) > 0.8;
\end{minted}

执行结果见 Table \ref{table:result}。

\begin{table}
	\centering
	\begin{tabular}{|c|c|c|}
		\hline
		语句行号 & 执行结果 & 执行时间 \\
		\hline
		1 & 3252 & 8552.418 ms \\
		2 & 2112 & 17031.994 ms \\
		3 & 2347 & 41105.923 ms \\
		4 & 2199 & 54372.745 ms \\
		\hline
	\end{tabular}
	\caption{四条SQL语句执行结果}
	\label{table:result}
\end{table}

\section{性能优化}

Levenshtein Distance算法的时间复杂度是$O(m\times n)$，我没有想到更好的优化方法。不过空间上由于每次外层循环都只用到了两行的数组数据，所以实际上只需要两行的数组数据就可以完成所有操作。不过考虑到这对时间复杂性没有影响，所以没去做这个优化。

Jaccard Index计算我的想法是将所有的bigram不重复地添加到一个数据结构中，每个节点通过一个标记记录bigram在两个字符串中的出现情况。这样我只需要一直插入，对于两个字符串，做不同的标记，最后数据结构中所有的节点数就是并集的元素个数，而所有同时有两个标记的节点就是交集中的元素。具体来说，标记只需要两个位就够了，所以存放在一个\incode{char}结构中足矣。而bigram只有两个字节，完全可以放在一个\incode{int}变量中，而且还方便进行大小的比较和排序。

对于该数据结构的考虑，最初我考虑过用256个链表的方式保存字符串的bigram，然后256个链表保存为一个数组。其中数组下标表示第一个字符，链表中再保存第二个字符。不过我觉得这样的效率明显不够高，如果某个字母的出现频率很高而且以它开头的bigram很多的情况下，很长的链表结构会拖慢查找效率。然后我开始考虑使用二叉树，将bigram保存到一个\incode{int}变量中，就可以对其进行大小排序。为了防止二叉树退化成链表，所以一定要用平衡二叉树。之后又在网上找了相关资料，发现了Size Balanced Tree，它以子树的大小作为二叉树调整依据，而且调整操作并不十分复杂。另一方面，整个二叉树的大小刚好就是集合元素个数，这对后面计算并集元素十分方便。

在时间复杂度上，平衡二叉树的插入操作时间复杂度是$O(\log N)$，总体上在插入上的时间复杂度为$O(N\log N)$，后面\incode{getValueCount()}函数的时间复杂度是$O(N)$，所以算法整体的时间复杂度为$O(N\log N)$，所以我最终愉快地选择了SBT。在此基础上，我找不到更好的优化方法了。

\end{document}
